package dynamic_programming;

import java.util.Arrays;

/**
 * 访问数组中的位置使分数最大 - 2786
 */
public class 访问数组中的位置使分数最大 {
    public static void main(String[] args) {
        int[] nums = {2, 3, 6, 1};
        System.out.println(new 访问数组中的位置使分数最大().maxScore(nums, 5));
    }

    public long maxScore(int[] nums, int x) {
        int n = nums.length; // 数组长度
        long[][] memo = new long[n][2]; // 记忆数组，用于存储状态值

        // 初始化记忆数组
        for (long[] ints : memo) {
            Arrays.fill(ints, -1); // 将所有值初始化为 -1
        }

        // 调用深度优先搜索函数，从索引 0 开始，初始状态为 nums[0] % 2，目标得分差值 x
        return dfs(0, nums[0] % 2, nums, x, memo);
    }

    /**
     * 深度优先搜索函数，计算从索引 i 开始的最大得分
     * @param i 当前考虑的索引
     * @param j 当前索引 i 的奇偶性（0 或 1）
     * @param nums 输入的整数数组
     * @param x 目标得分差值
     * @param memo 记忆数组，存储已经计算过的状态值
     * @return 从索引 i 开始的最大得分
     */
    private long dfs(int i, int j, int[] nums, int x, long[][] memo) {
        if (i == nums.length) return 0; // 达到数组末尾，返回得分 0

        if (memo[i][j] != -1) return memo[i][j]; // 如果当前状态已经计算过，直接返回记忆数组中的值

        // 当前数与当前索引的奇偶性不匹配，递归跳过当前数
        if (nums[i] % 2 != j) return memo[i][j] = dfs(i + 1, j, nums, x, memo);

        // 分别计算选择当前数或不选择当前数的情况，更新记忆数组
        long ans1 = dfs(i + 1, j, nums, x, memo); // 不选择当前数的得分
        long ans2 = dfs(i + 1, j ^ 1, nums, x, memo); // 选择当前数的得分

        // 返回当前状态的最大得分，考虑目标得分差值 x
        return memo[i][j] = Math.max(ans1, ans2 - x) + nums[i];
    }




}
